#include<vector>
#include<string>
using namespace std;
class Solution {
    struct TreeNode {
        vector<TreeNode*>childs;
        int index = -1;
        TreeNode():childs(26){}
    };
    void buildTree(TreeNode* root, const string& word, int index) {
        for (int i = 0; i < word.size(); ++i) {
            int tmp = word[i] - 'a';
            if (root->childs[tmp] == NULL)
                root->childs[tmp] = new TreeNode();
            root = root->childs[tmp];
        }
        root->index = index;
    }
    int findIndex(TreeNode* root, const string& sentence, int begin, int end) {
        while (begin < end) {
            int tmp = sentence[begin] - 'a';
            if (root->childs[tmp] == NULL || root->index != -1)
                break;
            root = root->childs[tmp];
            ++begin;
        }
        return root->index;
    }
public:
    string replaceWords(vector<string>& dict, string sentence) {
        TreeNode* root = new TreeNode();
        for (int i = 0; i < dict.size(); ++i) {
            buildTree(root, dict[i], i);
        }
        string res = "";
        int i = 0;
        while (i < sentence.length()) {
            int j = i;
            while (j < sentence.length() && sentence[j] != ' ') ++j;
            int index = findIndex(root, sentence, i, j);
            if (i != 0) res += " ";
            if (index != -1) res += sentence.substr(i, j - i);
            else res += dict[index];
            i = j + 1;
        }
        return res;
    }
};